|
In theoretical computer science and coding theory, the long code is an error-correcting code that is locally decodable. Long codes have an extremely poor rate, but play a fundamental role in the theory of hardness of approximation. ==Definition== Let for be the list of ''all'' functions from . Then the long code encoding of a message is the string where denotes concatenation of strings. This string has length . The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions that are linear functions when interpreted as functions on the finite field with two elements. Since there are only such functions, the block length of the Walsh-Hadamard code is . An equivalent definition of the long code is as follows: The Long code encoding of is defined to be the truth table of the Boolean dictatorship function on the th coordinate, i.e., the truth table of with .〔Definition 7.3.1 in ( Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes) )〕 Thus, the Long code encodes a -bit string as a -bit string. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Long code (mathematics)」の詳細全文を読む スポンサード リンク
|